#include <bits/stdc++.h>
using namespace std;

// 【题目】556. 下一个更大元素 III
// 【难度】中等
// 【提交】2025.9.25 https://leetcode.cn/problems/next-greater-element-iii/submissions/665956526
// 【标签】字符串
class Solution {
public:
    int nextGreaterElement(int n) {
    auto tmp = to_string(n);
    return next_permutation(tmp.begin(),tmp.end()) && stol(tmp) <= INT_MAX ? stol(tmp) : -1;   
    }
};

/**
 * @brief 学习总结：
 * 学到了to_string(), stol(), next_permutation()的用法，还学到了三元运算符return (A) && (B) ? C : D;
*/


/*
--------------------------------------------------------------------------------------------------------------
（学习笔记：LeetCode 556「下一个更大元素 III」
（提交记录：2024-03-25，C++，用时 4 ms，内存 6.5 MB）

一、题意与模型
给定一个正整数 n，要求找到一个由 n 中的数字重新排列得到的下一个更大的整数。如果不存在这样的整数，则返回 -1。需要注意的是：
返回的整数必须是一个 32 位整数。如果找到的结果超出 32 位整数的范围，也需要返回 -1。

二、标准 DP 状态设计
通过重新排列 n 中的数字来找到下一个更大的整数。可以使用字典序来找到下一个排列。
需要注意的是，返回的整数应在 32 位整数范围内，因此需要确保答案在 INT_MAX 范围内。

三、你的实现思路
利用 next_permutation 函数：通过 C++ STL 中的 next_permutation 函数来得到下一个字典序更大的排列。
处理溢出情况：利用 stol 将字符串转换回整数后，检查其是否超出了 32 位整数的范围。如果超出，返回 -1。
边界条件：如果没有找到下一个更大的排列（next_permutation 返回 false），则返回 -1。

四、逐行注释（带细节提醒）
cpp

class Solution {
public:
int nextGreaterElement(int n) {
auto tmp = to_string(n); // 将整数转换为字符串以便操作
return next_permutation(tmp.begin(), tmp.end()) && stol(tmp) <= INT_MAX ? stol(tmp) : -1;
// 使用 next_permutation 获取下一个排列，如果存在且小于等于 INT_MAX 则返回，否则返回 -1
}
};

五、正确性证明
next_permutation 函数确保我们找到的是 n 的下一个字典序排列。
如果排列存在，且转换后的整数不超过 32 位整数范围，则返回该整数。
如果不存在下一个排列，或者超出了 32 位整数的范围，则返回 -1。

六、复杂度
时间：O(d)，其中 d 为 n 的位数。next_permutation 的时间复杂度为 O(d)，因为它需要遍历整个数字数组。
空间：O(d)，由于将整数转换为字符串进行操作，所以空间复杂度为 O(d)，其中 d 是 n 的位数。

七、优缺点分析
优点：
时间复杂度为 O(d)，对于较小的整数非常高效。
利用 next_permutation 函数简化了代码，避免了手动实现排列的复杂性。

缺点：
对于非常大的数字，next_permutation 需要对字符串进行操作，可能会导致空间使用较高。
如果结果超出 32 位整数的范围，需要进行额外的判断和处理。

八、改进建议
当前算法已经非常简洁，若进一步优化，可考虑避免将整数转化为字符串，从而减少空间使用。
对于非常大的 n，可能需要优化溢出的处理逻辑，但对于本题范围内的问题来说，这已经是最优解法。

九、一句话总结
该题通过利用 C++ 的 next_permutation 函数，结合字符串操作，简洁地解决了寻找下一个更大排列的问题，并保证结果在 32 位整数范围内，时间复杂度为 O(d)，空间复杂度为 O(d)，非常高效且易于实现。
--------------------------------------------------------------------------------------------------------------
*/